module Abb ( Abb,
	abb_empty,
	abb_add,
	abb_search,
	abb_del,
	abb_toListPair)
where
data Abb a b = Branch a b (Abb a b) (Abb a b) | Leaf
	deriving Show
	
abb_empty :: Abb a b
abb_empty = Leaf

abb_add :: Ord a => Abb a b -> a -> b -> Abb a b
abb_add Leaf x y = Branch x y Leaf Leaf
abb_add x@(Branch ni nd ri rd) a b	|a == ni = x
					|a > ni = Branch ni nd ri (abb_add rd a b)
					|a < ni = Branch ni nd (abb_add ri a b) rd
					
abb_search :: Ord a => Abb a b -> a -> Maybe b
abb_search Leaf a = Nothing
abb_search (Branch ni nd ri rd) a 	|a == ni = Just nd
					|a > ni = abb_search rd a
					|a < ni = abb_search ri a
					
abb_toListPair :: Ord a => Abb a b -> [(a,b)]
abb_toListPair Leaf = []
abb_toListPair (Branch ni nd ri rd) = abb_toListPair ri ++ [(ni,nd)] ++ abb_toListPair rd


abb_min :: Abb a b -> Maybe (a, b)
abb_min Leaf = Nothing
abb_min (Branch ni nd Leaf rd) = Just (ni,nd)
abb_min (Branch ni nd ri rd) = abb_min (ri)

abb_del :: Ord a => Abb a b -> a -> Abb a b
abb_del Leaf _ = Leaf
abb_del (Branch ni nd ri rd) a 	| a == ni = case abb_min rd of
                                                        Nothing -> ri
                                                        Just (m,n)-> Branch m n ri (abb_del rd m)
                                | a > ni = Branch ni nd ri (abb_del rd a)
                                | a < ni = Branch ni nd (abb_del ri a) rd





